package leetcode_1000;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;

/**
 *@author 周杨
 *ReorderLogFiles_937 对字符串进行特殊排序 
 *describe:用优先队列和hashmap实现 AC 75%
 *2018年11月21日 下午1:31:49
 */
public class ReorderLogFiles_937 {
	public static void main(String[] args) {
		ReorderLogFiles_937 test=new ReorderLogFiles_937();
		test.reorderLogFiles(new String[] {"a1 9 2 3 1","g1 act car","zo4 4 7","ab1 off key dog","a8 act zoo"});
	}
	
	
	public String[] reorderLogFiles(String[] logs) {
        List<String> digits=new ArrayList<String>();
        Map<String,List<Integer>> map=new HashMap<String,List<Integer>>();
        PriorityQueue<String> queue=new PriorityQueue<String>();
        for(int i=0;i<logs.length;++i) {
        	String now=logs[i].substring(logs[i].indexOf(" ")+1);//从第一个空格开始截取
        	if(Character.isDigit(now.charAt(0)))
        		digits.add(logs[i]);
        	else {
        		queue.offer(now);
        		List<Integer> list=map.get(now);
        		if(list==null)
        			list=new ArrayList<Integer>();
        		list.add(i);
        		map.put(now, list);
        	}
        	
        }
        String[] res=new String[logs.length];
        int index=0;
        while(!queue.isEmpty()) {
        	String now=queue.poll();
        	for(int i:map.get(now))
        		res[index++]=logs[i];
        }
        for(String s:digits)
        	res[index++]=s;
        return res;
    }
}
